from typing import Generic, TypeVar, List
T = TypeVar('T')

class Node(Generic[T]):
    _value: int
    _parent: 'Node[T]'
    _children: List['Node[T]']
    _subtree_size: int
    
    def __init__(self, value: T) -> None:
        self._value = value
        self._parent = None
        self._children = []
        self._subtree_size = 1
            
    def get_value(self) -> T:
        return self._value

    def set_value(self, value: T) -> None:
        self._value = value
        
    def get_parent(self) -> 'Node[T]':
        return self._parent    
        
    def get_subtree_size(self) -> int:
        return self._subtree_size

    def set_subtree_size(self, value: int) -> None:
        self._subtree_size = value
        
    def add_child(self, child: 'Node[T]') -> None:
        self._children.append(child)
        child._parent = self

    def get_children(self) -> List['Node[T]']:
        return self._children

    def num_children(self) -> int:
        return len(self._children)

    def is_internal(p: 'Node[T]') -> bool:
        return len(p._children) != 0 # 有子节点
        
    def is_external(p: 'Node[T]') -> bool:
        return len(p._children) == 0 # 无子节点

    def is_root(p: 'Node[T]') -> bool:
        return p._parent == None
    
    def get_fromRoot_id(p: 'Node[T]') -> int:
        offset_id = 0
        while p.get_parent():
            offset_id += 1
            p = p.get_parent()
        return offset_id
    
class Tree(Generic[T]):
    _size: int
    _root: Node[T]
 
    def __init__(self, root: 'Node[T]') -> None:
        self._root = root
        self._size = 0
        if root != None:
            self._size = 1
            
    def get_root(self) -> 'Node[T]':
        return self._root
    
    def get_size(self) -> int:
        return self._size
    
    def is_empty(self) -> bool:
        return self._root == None  
 
    def is_root(self, p: 'Node[T]') -> bool:
        if p is None:
            return False
        return p.get_parent() == None
    
    def is_leaf(self, p: 'Node[T]') -> bool:
        if p is None:
            return False
        return p.is_external()

    def add_node(self, p: 'Node[T]', parent: 'Node[T]') -> None:
        if self._root is None and p != None and parent is None:
            self._root = p
            self._size += 1
            
        elif (p is None) or (parent is None):
            return
        
        else:
            parent.add_child(p)
            self._size += 1
            if self._root is None:
                self._root = parent
                self._size += 1
 
        # Update subtree size for parent and all its ancestors.
        while p.get_parent() != None:
            p = p.get_parent()
            p_subtree = p.get_subtree_size()
            p.set_subtree_size(p_subtree + 1)
 
    def remove_node(self, p: 'Node[T]') -> None: # 连带移除子树？
        if p is None:
            return
 
        if p.is_root():
            self._root = None
            self._size = 0
        else:
            current = p
            subtree_size = p.get_subtree_size()
            while p.get_parent() != None:
                p = p.get_parent()
                p.set_subtree_size(p.get_subtree_size() - subtree_size)
            parent = current.get_parent()
            parent.get_children().remove(current)
            self._size -= subtree_size
            
    def preorder(self, p: 'Node[T]', ls: List['Node[T]']) -> None:
        if p is None:
            return
 
        ls.append(p)
        for child in p._children:
            self.preorder(child, ls)
    
    def postorder(self, p: 'Node[T]', ls: List['Node[T]']) -> None:
        if p is None:
            return
        
        for child in p._children:
            self.postorder(child,ls)
        ls.append(p)

class DST(Tree): # Dynamic Spanning Tree 动态可变生成树
    _size: int
    _root: Node[T]
    
    def __init__(self, root: 'Node[T]') -> None:
        super(DST, self).__init__(root)
        
    def remove_node(self, p: 'Node[T]') -> None: # 子树继承
        if p is None:
            return
 
        if p.is_root(): # 移除根节点
            if self._root.is_internal():    # 有子节点 
                for child_node in self._root.get_children():
                    if child_node != self._root.get_children()[0]:
                        self._root.get_children()[0].add_child(child_node)
                self._root = self._root.get_children()[0]
                self._size -= 1
            else:
                self._root = None
                self._size = 0
            
        else:   # 移除普通节点
            current = p
            # subtree_size = p.get_subtree_size()
            while p.get_parent() != None:
                p = p.get_parent()
                p.set_subtree_size(p.get_subtree_size() - 1)
            parent = current.get_parent()
            # print(parent.get_value())
            # print(parent.get_children()[0].get_value())
            parent.get_children().remove(current)
            self._size -= 1
            if current.is_internal():
                for child_node in current.get_children():
                    parent.add_child(child_node)
    
    def get_subtree(self, p: 'Node[T]') -> None:
        if p is None:
            return 
        
        edges = []
        if p.is_internal():
            for child in p.get_children():
                subEdges = self.get_subtree(child)
                edges.append((p.get_value(), child.get_value()))
                edges.append(subEdges)
            
        return edges
    

        
if __name__ == "__main__":
    
    root_num = 1
    root_node = Node(root_num)
    tree = Tree(root_node)
    
    print(tree._root._value)
    